1. Huffman-Codierung ¹

David Huffman hat 1952 ein Verfahren entwickelt, mit welchem Zeichen platzsparender codiert werden können. Seine Idee ist, dass Zeichen, welche häufig im Text vorkommen, einen kürzeren Code erhalten, als Zeichen, welche selten im Text vorkommen.

Alltagsbezug

Die Huffman-Codierung und ähnliche Verfahren werden für das Komprimieren von Dateiformaten wie DOCX, JPG oder MP3 eingesetzt. ²

Codebaum

Ein Codebaum ist eine Struktur mit einem Startknoten. Von diesem aus geht es entweder nach links oder rechts unten weiter. Eine 0 im Code bedeutet nach links gehen, eine 1 nach rechts gehen. Wenn ein Knoten mit einem Buchstaben erreicht wird, hat man ein Zeichen decodiert, man beginnt wieder von vorne.

Erstellen eines Huffman-Baumes

Am Beispiel der Codierung des Texts «EINTRITT FREI» soll der Huffman-Algorithmus erläutert werden.

Zuerst zählt man, wie oft jedes Zeichen im Text vorkommt und erstellt eine Häufigkeitstabelle.

Zeichen	Häufigkeit
␣	1
F	1
N	1
R	2
E	2
I	3
T	3

Nun geht es darum, einen Codierungsbaum zu erstellen. Die Häufigkeiten der Buchstaben bilden je einen Knoten. Die Häufigkeit steht im Knoten, der Buchstaben darunter. Die Knoten werden nach Häufigkeit sortiert:

Nun werden die zwei Knoten mit den kleinsten Häufigkeiten an einen neuen Knoten angehängt. Der neue Knoten enthält die Summe der Häufigkeiten der ursprünglichen Knoten und wird gemäss der Summe neu eingeordnet.

Dies wird wiederholt bis alle Knoten miteinander verbunden sind. Wenn zwei Knoten die gleiche Häufigkeit haben, spielt es keine Rolle, welcher gewählt wird. Im nächsten Schritt wird der kleinste Knoten «N» mit «R» zusammengefasst. Man könnte aber «N» auch mit «E» oder dem neuen Knoten «2» zusammenfassen.

Wichtig ist, dass immer die kleinsten Knoten zusammengefasst werden. Hier werden die zwei Knoten mit Häufigkeit 2 zusammengefasst:

Wenn der Baum fertig ist, werden alle Äste, welche nach links zeigen, mit einer «0» markiert, alle die nach rechts zeigen mit einer «1».

Nun kann eine Codierungstabelle erstellt werden, indem der Code für jedes Zeichen vom Baum abgelesen wird:

Zeichen	Code
I	00
T	01
N	100
R	101
E	110
⎵	1110
F	1111

Zusammenfassung

Übungen

1. Decodieren

Decodieren Sie diese Bitfolge mit dem obenstehenden Codebaum. Das Symbol ⎵ steht für das Leerzeichen.

0111101011000110110101

SSR

2. Huffman-Codierung 1

1. Erstellen Sie zum Wort «MISSISSIPPI» eine Häufigkeitstabelle.
2. Erstellen Sie einen Huffman-Baum. (Laden Sie ein Foto davon hier hoch)
3. Codieren Sie das Wort.
4. Angenommen, der Text würde mit UTF-8 codiert. Wie viele Bits wurden mit der Huffman-Codierung eingespart?
5. Angenommen die 4 Buchstaben werden mit einer naiven Codierung ohne Huffman-Baum codiert. Wie viele Bits wären dann nötig? Wie viele Bits werden im Vergleich dazu eingespart?

SSR

SSR

3. Huffman-Codierung 2

1. Erstellen Sie zum Wort «EXTERNER EFFEKT» eine Häufigkeitstabelle.
2. Erstellen Sie einen Huffman-Baum. (Laden Sie ein Bild davon hier hoch).
3. Codieren Sie das Wort.
4. Wie viele Bits können durch die Huffman-Codierung hier im Vergleich zu (i) UTF-8 und (ii) zu einer naiven Codierung eingespart werden?
5. Bei welcher Art von Text würden Sie diese allenfalls eher einsetzen?

SSR

SSR

Take-Home Message

SSR

---

1. Quelle: S. Rothe, T. Jampen, R. Meyer↩
2. Quelle: Wikipedia: Huffman coding↩